We propose a stronger formulation of the precedence constraints and thestation limits for the simple assembly line balancing problem. The linearrelaxation of the improved integer program theoretically dominates all previousformulations using impulse variables, and produces solutions of significantlybetter quality in practice. The improved formulation can be used to strengthenrelated problems with similar restrictions. We demonstrate their effectivenesson the U-shaped assembly line balancing problem and on the bin packing problemwith precedence constraints.
展开▼
